import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Test {
    /***
     *力扣438，找到字符串中所有单词的异位词起始位置
     * 算法:滑动窗口
     */
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ret = new ArrayList<Integer>();
        char[] ch1 = s.toCharArray();//字符串转换为字符数组
        char[] ch2 = p.toCharArray();

        //使用数组模拟哈希表节约耗时
        int[] hash1 = new int[26];
        int[] hash2 = new int[26];
        for (int i = 0; i < ch2.length; i++) {
            hash1[ch2[i] - 'a']++;
        }
        int m=ch2.length;
        for(int left=0,right=0,count=0;right<ch1.length;right++){
            char in=ch1[right];
            hash2[in-'a']++;//进窗口
            if(hash2[in-'a']<=hash1[in-'a']){//维护count
                count++;
            }
            if(right-left+1>m){//判断
                char out=ch1[left++];
                if(hash2[out-'a']--<=hash1[out-'a']){
                    count--;
                }
            }
            if(count==m){
                ret.add(left);//更新结果
            }
        }
        return ret;
    }


    public List<Integer> findAnagrams1(String ss, String pp) {
        List<Integer> ret=new ArrayList<>();
        if(ss.length()<pp.length()){
            return ret;
        }
        char[] s=ss.toCharArray();
        char[] p=pp.toCharArray();
        Map<Character,Integer> hash1=new HashMap<>();
        Map<Character,Integer> hash2=new HashMap<>();
        for(char ch:p){
            hash1.put(ch,hash1.getOrDefault(ch,0)+1);
        }
        for(int left=0,right=0;right<s.length;right++){
            //进窗口
            char in=s[right];
            hash2.put(in,hash2.getOrDefault(in,0)+1);
            //判断
            while(right-left+1>p.length){//窗口长度超过指定字符串长度的时候进行出窗口
                char out=s[left++];
                if(hash2.get(out)==1){
                    hash2.remove(out);
                }else{
                    hash2.put(out,hash2.get(out)-1);//窗口中当前计数超过1就当前计数减一，使长度不超过窗口
                }
            }
            //更新结果
            if(right-left+1==p.length){
                if(hash1.equals(hash2)){
                    ret.add(left);
                }
            }
        }
        return ret;
    }
    public static void main(String[] args) {
        String s="cbaebabacd";
        String p="abc";
        Test t=new Test();
        System.out.println(t.findAnagrams1(s,p));
    }
}
